updated: 2022-01-23_12:32:31-05:00

DFA

  • Deterministic Finite Automata
  • Every state needs to have a transition for every possible input
    • ^^ this is what makes it Deterministic
  • A language that is represented by this is a Regular Language

Formal Definition

Pasted image 20210910092450

Examples

  1. Suppose $\Sigma={0,1,2,3,4,5,6,7,8,9}$
    • Design a DFA for languages of strings that have the property that the sum of digits is a multiple of three
    • Going to use % operator
    • Three states: modulus is either 0,1,2
      • We accept 0

Pasted image 20210910093740